import java.util.LinkedList;
import java.util.List;

public class Solution641 {

    private class Node{
        int val;
        Node next;
        Node last;
        Node(int val){
            this.val=val;
            next=null;
            last=null;
        }
    }

    int tmpLen;
    final int size;
    Node head;
    Node tail;

    /** Initialize your data structure here. Set the size of the deque to be k. */
    public Solution641(int k) {
        size=k;
        tmpLen=0;
        head=null;
        tail=null;
    }

    void initQueue(Node tmp){
        head=tmp;
        tail=tmp;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        tmpLen++;
        Node newHead=new Node(value);
        if(tmpLen==1){
            initQueue(newHead);
            return true;
        }
        newHead.next=this.head;
        this.head.last=newHead;
        this.head=newHead;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }
        tmpLen++;
        Node newTail=new Node(value);
        if(tmpLen==1){
            initQueue(newTail);
            return true;
        }
        this.tail.next=newTail;
        newTail.last=tail;
        this.tail=newTail;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }
        tmpLen--;
        this.head=this.head.next;
        if(head!=null)
            head.last=null;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if(isEmpty()){
            return false;
        }
        tmpLen--;
        tail=tail.last;
        if(tail!=null)
            tail.next=null;
        return true;
    }

    /** Get the front item from the deque. */
    public int getFront() {
        if(isEmpty()){
            return -1;
        }
        return head.val;
    }

    /** Get the last item from the deque. */
    public int getRear() {
        if(isEmpty()){
            return -1;
        }
        return tail.val;
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return tmpLen==0;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return tmpLen==size;
    }
}
